翻訳と辞書 Words near each other ・ Vizianagaram (Assembly constituency) ・ Vizianagaram (Lok Sabha constituency) ・ Vizianagaram district ・ Vizianagaram estate ・ Vizianagaram mandal ・ Vizianagaram railway station ・ ViziApps ・ VizieR ・ Vizier ・ Vizier (Ancient Egypt) ・ Vizier (Ebla) ・ Vizier's fingers ・ Vizija (band) ・ Vizille ・ Vizinex RFID ・ Vizing's conjecture ・ Vizing's theorem ・ Vizio ・ Vizion air ・ Vizion Plus ・ Vizioz ・ Viziru ・ Vizitiu ・ Vizitsa ・ Vizić ・ Vizma ・ Vizma Belševica ・ Vizma River ・ Vizmanos ・ Viznah Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Vizing's conjecture ： ウィキペディア英語版 Vizing's conjecture In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by , and states that, if γ(''G'') denotes the minimum number of vertices in a dominating set for ''G'', then : $\backslash gamma(G\backslash ,\backslash Box\backslash ,H)\; \backslash ge\; \backslash gamma(G)\backslash gamma(H).\; \backslash ,$ conjectured a similar bound for the domination number of the tensor product of graphs; however, a counterexample was found by . Since Vizing proposed his conjecture, many mathematicians have worked on it, with partial results described below. For a more detailed overview of these results, see . == Examples == A 4-cycle ''C''4 has domination number two: any single vertex only dominates itself and its two neighbors, but any pair of vertices dominates the whole graph. The product $C\_4\; \backslash ,\backslash Box\backslash ,C\_4$ is a four-dimensional hypercube graph; it has 16 vertices, and any single vertex can only dominate itself and four neighbors, so three vertices could only dominate 15 of the 16 vertices. Therefore, at least four vertices are required to dominate the entire graph, the bound given by Vizing's conjecture. It is possible for the domination number of a product to be much larger than the bound given by Vizing's conjecture. For instance, for a star K1,''n'', its domination number γ(K1,''n'') is one: it is possible to dominate the entire star with a single vertex at its hub. Therefore, for the graph $G\; =\; K\_\backslash ,\backslash Box\backslash ,K\_$ formed as the product of two stars, Vizing's conjecture states only that the domination number should be at least 1 × 1 = 1. However, the domination number of this graph is actually much higher. It has ''n''2 + 2''n'' + 1 vertices: ''n''2 formed from the product of a leaf in both factors, 2''n'' from the product of a leaf in one factor and the hub in the other factor, and one remaining vertex formed from the product of the two hubs. Each leaf-hub product vertex in ''G'' dominates exactly ''n'' of the leaf-leaf vertices, so ''n'' leaf-hub vertices are needed to dominate all of the leaf-leaf vertices. However, no leaf-hub vertex dominates any other such vertex, so even after ''n'' leaf-hub vertices are chosen to be included in the dominating set, there remain ''n'' more undominated leaf-hub vertices, which can be dominated by the single hub-hub vertex. Thus, the domination number of this graph is $\backslash gamma(K\_\backslash ,\backslash Box\backslash ,K\_)\; =\; n+1$ far higher than the trivial bound of one given by Vizing's conjecture. There exist infinite families of graph products for which the bound of Vizing's conjecture is exactly met.〔; ; ; .〕 For instance, if ''G'' and ''H'' are both connected graphs, each having at least four vertices and having exactly twice as many total vertices as their domination numbers, then $\backslash gamma(G\backslash ,\backslash Box\backslash ,H)=\backslash gamma(G)\backslash gamma(H)$.〔.〕 The graphs ''G'' and ''H'' with this property consist of the four-vertex cycle ''C''4 together with the rooted products of a connected graph and a single edge.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vizing's conjecture」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.